package com.sunny;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Spliterator;
import java.util.function.Consumer;

public class LRUCache2<K,V>{

    private HashMap<K, Node<K,V>> map = new HashMap<>();
    private Node head;
    private Node tail;

    private int cap;

    public LRUCache2(int cap) {
        this.cap = cap;
    }

    public void print(){
        map.forEach((k,v)->{
            System.out.println(k+" "+v.val);
        });
    }

    public Node<K,V> get(K k){
        if(!map.containsKey(k)){
            return null;
        }
        Node res = map.get(k);
        if(head.key.equals(res.key)){
            return res;
        }
        res.prev.next = res.next;
        if(null != res.next)
            res.next.prev = res.prev;
        res.prev = null;
        res.next = head;
        head.prev = res;
        return res;
    }

    public void put(K k, V v){

        Node node;
        if(map.containsKey(k)){
            if(k.equals(head.key)){
                head.val = v;
                return;
            }
            node = map.get(k);
            node.prev.next = node.next;
            if(null != node.next) {
                node.next.prev = node.prev;
            }else{
                //说明是tail
                tail = node.prev;
            }
            node.val = v;
            node.prev = null;
            node.next = head;
            head.prev = node;
            head = node;
        }else if(map.size() > 0){
            node = new Node(k,v);
            if(map.size()>=cap){
                map.remove(tail.key);
                Node tmp = tail.prev;
                if(null != tmp)
                    tmp.next = null;
                tail.prev = null;
                tail = tmp;
            }
            node.next = head;
            head.prev = node;
            head = node;
        }else{
            node = new Node(k,v);
            head = tail = node;
        }
        map.put(k, node);

    }

    public static void main(String[] args) {

        LRUCache2<String, String> cache = new LRUCache2<>(5);
        cache.put("a","s");
        cache.put("b","s");
        cache.put("c","s");
        cache.put("d","s");
        cache.put("e","s");
        cache.put("f","s");
        cache.put("b","s");
        cache.put("a","s");
        cache.put("i","s");
        cache.put("j","s");
        cache.put("a","s");

        cache.print();

    }

}

class Node<K,V>{
    K key;
    V val;

    public Node(K key, V val) {
        this.key = key;
        this.val = val;
    }

    Node prev;
    Node next;
}